package com.shuo.dsa.leetcode;

import com.shuo.dsa.model.Point;

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;

/**
 * 平面上一条直线上最大的point数
 *     思路: 2层遍历, 第一层全节点, 第二次从i+1开始直到结束
 */
public class MaxPointsOnLine {
    public static void main(String[] args) {
        Point p1 = new Point(4, 0);
        Point p2 = new Point(4, -1);
        Point p3 = new Point(4, 5);
        System.out.println(new MaxPointsOnLine().maxPoints(new Point[]{p1, p2, p3}));
    }

    public int maxPoints(Point[] points) {
        if (points.length == 0) return 0;
        if (points.length == 1) return 1;
        int len = points.length;
        int max = 0;
        for (int i = 0; i < len; i++) {
            Map<Double, Integer> map = new HashMap<>();
            Point p1 = points[i];
            int samePoint = 1;
            for (int j = i + 1; j < len; j++) {
                Point p2 = points[j];
                if (p1.x == p2.x && p1.y == p2.y) {
                    samePoint++;
                    continue;
                }
                incrValue(map, getSlope(p1, p2));
            }
            int tmpMax = getMax(map.values()) + samePoint;
            if (tmpMax > max)
                max = tmpMax;
        }
        return max;
    }

    private int getMax(Collection<Integer> array) {
        if (array.isEmpty())
            return 0;
        int max = Integer.MIN_VALUE;
        for (Integer i : array) {
            if (i > max)
                max = i;
        }
        return max;
    }

    private void incrValue(Map<Double, Integer> map, double key) {
        map.merge(key, 1, (a, b) -> a + b);
    }


    private double getSlope(Point p1, Point p2) {
        if (p2.y == p1.y)
            return Double.MAX_VALUE;
        // map中0.0和-0.0是不一样的key
        if (p1.x == p2.x)
            return 0;
        return ((double) (p1.x - p2.x)) / ((double) (p1.y - p2.y));
    }
}
